package 算法.其他算法;

public class JZ14剪绳子 {
    //动态规划
    public int cutRope(int target) {
        //不超过3直接计算
        if(target <= 3)
            return target- 1;
        //dp[i]表示长度为i的绳子可以被剪出来的最大乘积
        int[] dp = new int[target + 1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        dp[4] = 4;
        //遍历后续每一个长度
        for(int i = 5; i <= target; i++)
            //可以被分成两份
            for(int j = 1; j < i; j++)
                //取最大值
                dp[i] = Math.max(dp[i], j * dp[i - j]);
        return dp[target];
    }

    //贪心
    // 1 2 3 4  --- 2 * 4 < 3 * 3  --- (3)
    public int cutRope2(int target) {
        //不超过3直接计算
        if(target <= 3)
            return target - 1;
        int res = 1;
        while(target > 4){
            //连续乘3
            res *= 3;
            target -= 3;
        }
        return  res*target;
    }

    public int cutRope3(int target) {
        if(target<=2)
                return 1;
        if(target==3)
                return  2;
        int res = target / 3;
        int mod = target % 3;
        if(mod==0)
            return (int)Math.pow(3,res);
        else if(mod==1)
            return (int)(Math.pow(3,res-1) * 4);
        else
            return (int) Math.pow(3,res) * 2;
    }
}
